package NO16;

import java.util.Stack;

/**
 * 输入一个链表，反转链表后，输出链表的所有元素。
 * @author swg
 *
 */
public class ReverseList {
	public static class ListNode {
	    int val;
	    ListNode next = null;

	    ListNode(int val) {
	        this.val = val;
	    }
	}
	
    public static ListNode reverseList(ListNode head) {
    	//定义一个栈来存放节点
        Stack<ListNode> stack = new Stack<ListNode>();
        
        //遍历所有的节点并且将其放进栈中
        ListNode node = head;
        while(node != null){
            stack.push(node);
            node = node.next;
        }
        
        //定义两个头节点首先都先指向新构建的链表的头部
        //newFirst是用来形成新链表，所以是一直移动的
        //newFirstBak是永远停留在头节点，用于程序返回
        ListNode newFirst = null;
        ListNode newFirstBak = null;
        while(!stack.isEmpty()){
        	//如果是第一次创建链表
        	if(newFirst == null){
        		newFirst = new ListNode(stack.pop().val);
        		newFirstBak = newFirst;
        	}else{
        		//后面以此添加节点
        		ListNode temp = new ListNode(stack.pop().val);
        		newFirst.next = temp;
        		newFirst = newFirst.next;
        	}
        }
        //返回新构建的链表的头节点
        return newFirstBak;
    }
    public static void main(String[] args) {
		ListNode head = new ListNode(1);
		head.next = new ListNode(2);
		head.next.next = new ListNode(3);
		head.next.next.next = new ListNode(4);
		head.next.next.next.next = new ListNode(5);
		
		ListNode node = reverseList(head);
		System.out.println(node.val);
		System.out.println(node.next.val);
		System.out.println(node.next.next.val);
		System.out.println(node.next.next.next.val);
		System.out.println(node.next.next.next.next.val);
	}
}
